//
// Created by Rory on 2020/10/16.
//

#ifndef DATA_STRUCTURE_PROGRAMMING_USING_C_SEQUENTIALQUEUE_H
#define DATA_STRUCTURE_PROGRAMMING_USING_C_SEQUENTIALQUEUE_H


#include "../common.h"

/*
 * 顺序循环队列的策略选择
 * 一、队尾指针指向何处
 *     1. 指向队尾元素
 *     2. 指向队尾元素的下一个位置
 * 二、如何解决判空判满冲突
 *     1. 牺牲一个空间
 *     2. 辅助变量
 *          1). 增设一个表示队列长度的数据成员
 *          2). 增设一个boolean型的tag成员
 * 这两个方面的不同策略的选取组合将导致
 *     1. 队空，队满条件
 *     2. 队列长度的计算方式
 *     3. 入队出队具体操作（感觉是废话hhh）
 * 的不同
 * 本代码采用队尾指针指向队尾元素的下一个位置与牺牲一个空间的方式来实现循环队列
 * */

#ifndef ElemType
#define ElemType int
#endif


struct SeqCircularQueue__{
    int front;
    int rear;
    int capacity;
    bool autoExpand;//是否自动扩容
    ElemType data[0];
};
typedef struct SeqCircularQueue__* SCQueueP;//SCQueue Pointer
bool Enqueue(SCQueueP* queue, ElemType e);


/*
 * 创建初始化队列
 * */
SCQueueP CreateSCQueue(SCQueueP* queue, int capacity){
    if(capacity<1){
        return NULL;
    }
    (*queue) = (SCQueueP)malloc(sizeof(struct SeqCircularQueue__) + capacity*sizeof(ElemType));
    if((*queue)){
        (*queue)->capacity = capacity;
        (*queue)->front = (*queue)->rear = 0;
        (*queue)->autoExpand = true;
    }
    return (*queue);
}

/**
 * 打开自动扩容机制
 * @param queue
 * @param autoExpand
 */
void ChangeAutoExpandStausOfSCQueue(SCQueueP queue, bool autoExpand){
    queue->autoExpand = autoExpand;
}

/**
 * 队空判断
 */
bool IsEmpty(SCQueueP queue){
    return queue->rear == queue->front;
}

/**
 * 队满判断
 */
bool IsFull(SCQueueP queue){
    return (queue->rear + 1) % queue->capacity == queue->front;
}

/**
 * 队列长度
 * @param queue
 * @return
 */
int SizeOfSCQueue(SCQueueP queue){
    return (queue->rear+queue->capacity - queue->front) % queue->capacity;
}

/**
 * 自动扩容
 * @param queue
 * @return
 */
static bool AutoExpandOfSCQueue(SCQueueP* queue){
    DebugPrint("正在扩容...");

    SCQueueP temp = *queue;//保存原有空间
    int newSizeOfData = sizeof(ElemType)*(((*queue)->capacity+1)-1)*2;
    (*queue) = CreateSCQueue(queue,sizeof(struct SeqCircularQueue__) + newSizeOfData);
    if (*queue){
        (*queue)->capacity = newSizeOfData;
        //拷贝原有空间的数据到新空间
        int p = temp->front;
        while (p != temp->rear){
             Enqueue(queue,temp->data[p]);
            p = (p+1)%temp->capacity;
        }
        //释放原有空间
        free(temp);

        return true;
    }else{
        (*queue) = temp;
        return false;
    }
}

/**
 * 入队
 * @param queue : 队列指针
 * @param e : 入队元素
 * @return 入队是否成功
 */
bool Enqueue(SCQueueP* queue, ElemType e){
    if(IsFull(*queue)){
        if((*queue)->autoExpand){//内存不足，自动扩容
            if (!AutoExpandOfSCQueue(queue)){
                DebugPrint("内存不足！\n");
                return false;
            }
        } else{
            DebugPrint("内存不足！请打开扩容开关后冲试。\n");
            return false;
        }
    }

    (*queue)->data[(*queue)->rear] = e;
    (*queue)->rear = ((*queue)->rear + 1) % (*queue)->capacity;
    return true;
}

/**
 * 得到队头元素
 * @param queue
 * @param var
 * @return
 */
bool GetHeadOfSCQueue(SCQueueP queue,ElemType* var){
    if(!IsEmpty(queue)){
        *var = queue->data[queue->front];
        return true;
    }
    return false;
}


int GetLengthOfSCQueue(SCQueueP queue){
    return (queue->rear + queue->capacity - queue->front)%queue->capacity;
}

/**
 * 出队
 * @param queue
 * @param var 承载被删除的元素，请确保var指向合法空间，函数没有能力为var分配内存.
 */
bool DeQueue(SCQueueP* queue, ElemType* var){
        if(GetHeadOfSCQueue(*queue,var)){
            (*queue)->front = ((*queue)->front + 1) % (*queue)->capacity;
            return true;
        }
        return false;
}


/**
 * 销毁队列
 */
void DestroySCQueue(SCQueueP queue){
    free(queue);
}

void PrintIntSCQueue(SCQueueP queue){
    int p = queue->front;
    printf("\n");
    while (p != queue->rear){
        printf("%d ",queue->data[p]);
        p = (p+1)%queue->capacity;
    }
    printf("\n");
}
#endif //DATA_STRUCTURE_PROGRAMMING_USING_C_SEQUENTIALQUEUE_H
